package com.hyb.algorithm.data.struct.stack;

import com.hyb.algorithm.data.struct.tree.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ConcurrentLinkedDeque;

/**
 * @Author: huyanbing
 * @Date: 2021/8/12 3:20 下午
 * <p>
 * https://leetcode.wang/leetcode-111-Minimum-Depth-of-Binary-Tree.html
 * [3,9,20,null,null,15,7]
 */
public class MinDepth {

    /**
     * [3,9,20,null,null,15,7]
     *
     * @param args
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);

        root.left = new TreeNode(9);

        root.right = new TreeNode(20);

        root.right.left = new TreeNode(15);

        root.right.right = new TreeNode(7);

        MinDepth minD = new MinDepth();
        System.out.println(minD.minDepth(root));

    }

    public int minDepth(TreeNode root) {

        if(root==null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);

        int depth = 1;
        while (!queue.isEmpty()) {

            // 当前层元素的个数
            int levelNum=queue.size();

            //注意 要用 levelNum 不要用queue.size()   因为 queue.size() 一直在变化
            //相当于 将该层的 节点 都poll 出去
            for (int i = 0; i <levelNum; i++) {

                TreeNode node = queue.poll();

                if(node==null){
                    continue;
                }

                if (node.left == null && node.right == null) {
                    return depth;
                }

                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }

            }

            depth++;

        }

        return depth;
    }

}
